In the art of computer graphics, rendering of a primitive into an image in a three-dimensional graphics system requires a series of transformation steps. Generally, the Host Processor 10, of a system of the type illustrated in FIG. 1, will retrieve information describing the primitive from the System Memory 11 and provide same to the Graphics Subsystem 18. In the Graphics Subsystem, the Geometry Processor will perform a number of operations on the retrieved information in order to convert the information into a three-dimensional computer graphic. Once the geometry operations have been completed, the resulting representation of the image is rasterized in Rasterizer 13 and stored in the Local Memory 14 until it is read out of the Local Memory for display at Display Monitor 15. The series of geometric transformation operations include operations shown in the representative process flow of FIG. 2.
FIG. 2 shows that the original graphic information, described by application 20 in model coordinates, is first transformed from model coordinates into world coordinates via the Model Transformation step 21, whereby transformation matrices are applied to the primitive's coordinates, thereby transforming it into a unified coordinate system describing the position of all objects in the scene, referred to as world coordinates. At step 22, the primitive's world coordinates are further processed in the View Transformation step to render the image in eye coordinates, as if viewed from a single vantage point, with the human eye as the point of origin of the coordinate system.
The primitive in eye coordinates is next operated on in a way to add lighting and color to the coordinates, in the Lighting step 23. To this point in the graphics rendering process, all of the operations have simply been done on the Cartesian coordinates. In the Perspective Transformation step 24, the space is transformed into a box, such that the shape of the view volume is transformed to a normalized view volume in which the view plane is located at z=D and the eye at z=0. Perspective coordinates are then mapped into device coordinates in the Perspective Division step 25, yielding device coordinates which can be rasterized for display. The Rasterization processing breaks the display space down into pixels which must be set to the primitive's color where image components are present, and pixels which must be turned off, in image background areas.
After converting the image information into device coordinates, it is necessary to clip the image with respect to the view fustrum (i.e., field of view). Clipping is performed as step 26 prior to Rasterization at step 27. FIG. 3 provides a schematic illustration of the view fustrum 30 with several objects inside and outside of its boundaries. Under the prior art processing, objects, such as 31, which fall completely outside of the view volume were discarded from further processing ("trivial rejection"). Objects, such as 32, which fall entirely within the view volume remain unchanged and were sent directly to the rasterization subsystem ("trivial acceptance"). Objects, 33 and 34, that intersect the boundary of the view volume, however, required clipping against the view volume boundaries (also known as "clip planes"), such that those objects were split into multiple portions. Those portions of split or clipped objects which fall outside of the view volume were discarded, while the portions inside of the view volume were sent to the rasterizer. As is well known in the art, it is most advantageous to perform clipping on triangulated image components. With all vertices of the triangulated image lying in one plane, it is only necessary to know the vertices to perform clipping, without having to operate on each portion of the image volume lying within the vertices.
Clip testing, (i.e., determining whether a triangle can be trivially accepted or rejected) is commonly performed using clip codes for the triangle vertices. Clip codes contain one OUT bit for each clipping plane. The OUT bit is set if the vertex is outside the clipping plane associated with that bit. FIG. 4 shows a two-dimensional example of how clip codes are assigned to different regions formed by the clip planes 41-44. A triangle can be trivially accepted if the bitwise OR of the outcodes of all vertices is 00 . . . 0. A triangle can be trivially rejected if the bitwise AND of the outcodes of all vertices is not 00 . . . 0.
If a triangle cannot be trivially accepted or rejected, it needs to be clipped against the clip planes. A technique frequently used is described in Reentrant Polygon Clipping, Suntherland and Hodgman, CACM, Vol. 17, pages 32-42, (1974). The triangle is clipped successively against each clip boundary. Clipping is performed by determining the intersection of the triangle edges with the boundary. The intersection points with the boundary form new vertices with the clipped triangle(s). If two vertices lie outside of the clipping boundary, only one triangle is produced by the clipping step, as shown for image 50 in FIG. 5A which is clipped to triangle 51 of FIG. 5B. If only one vertex is clipped by the clipping plane, such as is shown for triangle 52 of FIG. 5A, two vertices are produced by the clipping step, shown as polygon 53 of FIG. 5B. After the triangle has been clipped against all clipping planes, the resulting polygon is retriangulated. From the example, it can be well appreciated that clipping can produce a variable number of output vertices/triangles depending on the input data.
FIG. 6 shows a flow diagram describing the steps involved in clipping a triangle. The triangle is provided for processing at step 60, after which the outcodes are computed for all vertices of the triangle, at step 61. If the outcodes indicated that all vertices are outside of the clip planes, then the triangle is trivially rejected at step 62. If not trivially rejected, the determination is made at step 63 as to whether all outcodes are within all clip planes for trivial acceptance of the triangle. For any remaining triangles, clipping is performed at step 64 along a first clip plane, followed by clipping along each of the remaining planes.
As taught in the co-pending application, entitled "METHOD AND APPARATUS FOR CLIPPING CONVEX POLYGONS ON SINGLE INSTRUCTION MULTIPLE DATA COMPUTERS", Ser. No. 08/898,747, which is assigned to the present assignee, if one utilizes a single instruction multiple data (SIMD) computer where one set of instructions may be applied to different data in parallel by a plurality of computer engines, the outcode analysis (i.e., comparisons) may be run in parallel on more than one of the SIMD engines. Similarly, once it has been determined by the control processor that clipping is necessary, the computationally intensive clipping steps may be performed in more than one engine at a time. However, to shift from one set of instructions to another (e.g., from outcode assignment to clipping for a single triangle along one plane), requiring reformatting of the data, constitutes a significant interruption of the parallel data flow and results in unacceptable performance penalties. Since the shifting from outcode analysis instruction to clipping instruction may be repeated many times as the contents of an image are evaluated along the six clipping planes, the process becomes unduly long and complex.
Further, algorithms typically used to clip a polygon against a convex view volume usually contain several tests and conditional execution paths that are selected and executed depending upon the input. In software implementations of polygon clipping, these branches limit the throughput of the processing pipeline because of misses in the instruction cache and limited prefetching across branch points. Clipping performance on SIMD computers is further hampered by the sequential nature of the clipping process. Consequently, only a small number of parallel execution units are generally active concurrently for a given input data set.
In addition, the variable output length of the clipping process may result in different dynamic instruction lengths on different engines of the SIMD processor, resulting in bad utilization of some compute engines. Maximization of SIMD engine utilization for clipping convex polygons is addressed in the aforementioned co-pending application. What is further desirable, however, is a method for optimizing the processing prior to providing the polygons for clipping.